package com.algorithm.dp;


/**
 * TODO manacher算法线性时间复杂度解决该问题
 */
public class LongestPalindromeSubString {
    public static void main(String[] args) {
        String max = longestPalindromeSubString("abcda");
        System.out.println(max);
    }

    static String longestPalindromeSubString(String s) {
        if (s.length() < 2) {
            return s;
        }
        int[][] dp = new int[s.length()][s.length()];
        int max = 1;
        int maxi = 0;
        int maxj = 0;

        for (int i = 0; i < s.length() - 1; i++) {
            dp[i][i] = 1;
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = 1;
                dp[i+1][i] = 1;
                max = 2;
                maxi = i;
                maxj = i+1;
            }
        }
        dp[s.length() - 1][s.length() - 1] = 1;
        /**
         * 也可以这样扫描:
         * for (int i = s.length() - 2; i >= 0; i--) {
         for (int j = i+1; j < s.length(); j++) {

         还可以优化为二维滚动数组
         */
        for (int j = 1; j < s.length(); j++) {
            for (int i = j - 1; i >= 0; i--) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                    if (max < j - i + 1 && dp[i][j] != 0) {
                        max = j - i + 1;
                        maxi = i;
                        maxj = j;
                    }
                } else {
                    dp[i][j] = dp[i][j] != 0 ? dp[i][j] : 0;
                }

            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }
        return s.substring(maxi,maxj +1);
    }

    /**
     * 使用一维数组优化
     */
    public static final int longestPalindromeSubString01(String s){
        return 0;
    }
}
